#include "header.h"
#include "fs.h"
#include <linux/slab.h>
#include <linux/namei.h>
#include <linux/mount.h>
#include <linux/dcache.h>
#include <linux/buffer_head.h>
#define E2PSFN(e) (e->prev_fn_source_dev)
#define B2MP(b) (b->bi_io_vec->bv_page->mapping)
#define B2IN(b) (b->bi_io_vec->bv_page->mapping->host)
#define B2SB(b) (b->bi_io_vec->bv_page->mapping->host->i_sb)
#define MK_RQ_FN(sb) (sb->s_bdev->bd_disk->queue->make_request_fn)
#define ROOT "/"
#define DELAY()						\
	set_current_state(TASK_UNINTERRUPTIBLE);	\
	schedule_timeout(HZ*5)

file_node* get_next_node(file_node* node) { 
	if (!node) return NULL;
	if (LC(node)) return LC(node);
	else if (RC(node)) return RC(node);
	else {
		while (PA(node) && (RC(PA(node))==node || !RC(PA(node)))) node = PA(node);
		if (PA(node) && LC(PA(node))==node && RC(PA(node))) return RC(PA(node));
		else return NULL;
	}
}

str_node* __remove_node(str_node* node) 
{
	str_node* next = node->next;
	kfree(node);
	return next;
}

int __is_excluded(struct dentry* dentry, file_node* excludeHead)
{
	while (excludeHead) {
		if (dentry == excludeHead->dentry) goto yes;
		excludeHead = excludeHead->nextSib;
	}
	return 0;
yes:
	return 1;
}

int __match(const char* name, const char* expression) 
{
	const char* next_exp = NULL;
	const char* next_name = NULL;
	while (true) {
		switch (*expression) {
		case '\0':
			return 1;

		case '^':
			if (*name) return 0;
			else return 1;
		
		case '.':
			next_exp = expression + 1;
			if (*next_exp) {
				if (*next_exp!='+' && *next_exp!='*') {
					if (*name) {++name; ++expression;}
					else return 0;
				} else if (*next_exp == '+') {
					if (*name) {
						next_name = name + 1;
						while (*next_name == *name) ++next_name;
						name = next_name;
						expression += 2;
					} else return 0;
				} else if (*next_exp == '*') {
					if (*name) {
						if (__match(name, expression+2)) return 1;
						else {
							next_name = name + 1;
							while (*next_name == *name) ++next_name;
							name = next_name;
							expression += 2;
						}
					} else return 1;
				}
			} else {
				if (*name) return 1;
				else return 0;
			}
			continue;

		case '\\':
			next_exp = expression + 1;
			if (!*next_exp) return 0;
			switch (*next_exp)
			{
			case '+':
				if (*name == '+') {
					++name;
					expression += 2;
					continue;
				} else return 0;
			case '*':
				if (*name == '*') {
					++name;
					expression += 2;
					continue;
				} else return 0;
			case '.':
				if (*name == '.') {
					++name;
					expression += 2;
					continue;
				} else return 0;
			default:
				++expression;
				continue;
			}			
			
		default:
			next_exp = expression + 1;
			if (*next_exp) {
				if (*next_exp!='+' && *next_exp!='*') {
					if (*name && *name==*expression) {
						++name;
						++expression;
					} else return 0;
				} else if (*next_exp == '+') {
					if (*name && *name==*expression) {
						next_name = name + 1;
						while (*next_name == *name) ++next_name;
						name = next_name;
						expression += 2;;
					} else return 0;
				} else if (*next_exp == '*') {
					if (*name) {
						if (__match(name, expression+2)) return 1;
						else if (*name == *expression) {
							next_name = name + 1;
							while (*next_name == *name) ++next_name;
							name = next_name;
							expression += 2;
						} else expression += 2;
					} else return 1;
				}
			} else {
				if (*name == *expression) return 1;
				else return 0;
			}
			continue;
		}
	}
	return 0;
}

int match(const char* name, const char* expression) 
{
	int ret = 0;
	if (!name || !expression) return 0;
	if (*expression == '$') return __match(name, ++expression);
	while (*name && !(ret=__match(name++, expression)));
	return ret;
}

int __is_filter_out(struct dentry* dentry, str_node* filterHead)
{
	while (filterHead) {
		if (match(dentry->d_name.name, filterHead->str)) goto yes;
		filterHead = filterHead->next;
	}
	return 0;
yes:
	return 1;
}

file_node* __addto_parent(file_node* parent, struct dentry* dentry)
{
	file_node* chd = NULL;
	file_node* preSib = NULL;
	if (!parent || !dentry) return NULL;
	chd = parent->firstChd;
	while (chd) {
		if (chd->dentry == dentry) return chd;
		preSib = chd;
		chd = chd->nextSib;
	} 
	chd = kmalloc(sizeof(file_node), GFP_KERNEL);
	memset(chd, 0, sizeof(file_node));
	chd->dentry = dentry;
	chd->parent = parent;
	if (preSib) preSib->nextSib = chd;
	else parent->firstChd = chd;
	return chd;
}

int __addto_parent_by_dentry(file_node* parent,
			     file_node* excludeList,
			     str_node* filterNode,
			     args_queue_elem* elem)
{
	file_node* fsTmp = NULL;
	file_node* preSib = NULL;
	struct dentry* dentry = NULL;
	struct list_head* next;
	if (!parent || !parent->dentry) return -1;

	parent->dentry->d_inode->i_private = elem;
	replace_make_request(parent->dentry->d_sb, elem);
	next = parent->dentry->d_subdirs.next;

	while (next != &parent->dentry->d_subdirs) {
		dentry = list_entry(next, struct dentry, d_u.d_child);

		if (STR_EQUAL(dentry->d_name.name, ".") || STR_EQUAL(dentry->d_name.name, "..")) {
			next = next->next;
			continue;
		}

		if ((S_ISDIR(dentry->d_inode->i_mode)&&__is_excluded(dentry, excludeList)) ||
		    (!S_ISDIR(dentry->d_inode->i_mode)&&__is_filter_out(dentry, filterNode))) {
			next = next->next;
			continue;
		} 

		if (!IS_EXT3(FSNAME(dentry->d_inode)) && 
                    !IS_EXT4(FSNAME(dentry->d_inode))) {
                        CAMERA_LOG("camera.ko found non-ext3/4 inode, exit building file tree");
                        return -1;
		}

		fsTmp = kmalloc(sizeof(file_node), GFP_KERNEL);
		memset(fsTmp, 0, sizeof(file_node));
		fsTmp->dentry = dentry;
		fsTmp->parent = parent;
		if (!parent->firstChd) {parent->firstChd = fsTmp; preSib = fsTmp;}
		else {preSib->nextSib = fsTmp; preSib = fsTmp;}
		__addto_parent_by_dentry(fsTmp, excludeList, filterNode, elem);
		next = next->next;
	}

        return 0;
}

int __addto_root_node(file_node* root, 
		      str_node* pathNode,
		      file_node* excludeList, 
		      str_node* filterNode,
		      args_queue_elem* elem) 
{
	char* path = NULL;
	struct nameidata nd;
	struct file_node* fsnHead = NULL;
	struct file_node* fsnTail = NULL;
	struct file_node* fsTmp = NULL;
	struct file_node* curRoot = NULL;
	struct vfsmount *mnt = NULL;
	if (!root || !pathNode) {
	        CAMERA_LOG("camera.ko encountered empty node, exit building tree.");
                return -1;
	} else path = pathNode->str;

	if (path_lookup(path, LOOKUP_FOLLOW, &nd)) {
		CAMERA_LOG("camera.ko driver failed to lookup path %s!\n", path);
		return -1;
	}	

	mnt = nd.path.mnt;
	fsnTail = kmalloc(sizeof(file_node), GFP_KERNEL);
	if (!fsnTail) {
	        CAMERA_LOG("camera.ko failed to alloc tail file node.");
		return -1;
	}

	memset(fsnTail, 0, sizeof(file_node));
	fsnTail->dentry = nd.path.dentry;
	fsnHead = fsnTail;

	while (fsnHead->dentry->d_parent != root->dentry) {
		fsTmp = kmalloc(sizeof(file_node), GFP_KERNEL);
		if (!fsTmp) {
		        CAMERA_LOG("camera.ko failed to alloc temporary file node");
                        return -1;
		}
		fsTmp->nextSib = fsTmp->firstChd = NULL;
		if (fsnHead->dentry == fsnHead->dentry->d_parent) {
		        fsTmp->dentry = mnt->mnt_mountpoint;
			mnt = mnt->mnt_parent;
		} else fsTmp->dentry = fsnHead->dentry->d_parent;
		fsTmp->firstChd = fsnHead;
		fsnHead = fsTmp;
	}

	fsTmp = fsnHead;
	curRoot = root;
	while (fsTmp) {
	        if(!(curRoot=__addto_parent(curRoot, fsTmp->dentry))) {
                        CAMERA_LOG("camera.ko failed to add node to tree.");
                        return -1;
                }
		fsTmp = fsTmp->firstChd;
	}

	if (__addto_parent_by_dentry(curRoot, excludeList, filterNode, elem)) {
                CAMERA_LOG("camera.ko failed to add node to parent node.");
                return -1;
        }
       
	while (fsnHead) {
		fsTmp = fsnHead;
		fsnHead = fsnHead->firstChd;
		kfree(fsTmp);
	}

	path_put(&nd.path);
	return 0;
}

void __releasefile_node(file_node* node) 
{
	if (!node) return;
	restore_make_request(node->dentry->d_sb);
	node->dentry->d_inode->i_private = NULL;
	__releasefile_node(node->firstChd);
	__releasefile_node(node->nextSib);
	kfree(node);
}

void release_camera_tree(file_node* root)
{
	if (!root) return;
	__releasefile_node(root);
}

ssize_t __kernel_write(struct file *file, const char *buf, 
		       size_t count, loff_t pos)
{
        mm_segment_t old_fs;
	ssize_t res;
	old_fs = get_fs();
	set_fs(get_ds());
	res = vfs_write(file, (const char __user *)buf, count, &pos);
	set_fs(old_fs);
	return res;
}

/*
  void print_indent(int indent)
  {
  int idx = 0;
  if (indent <= 0) return;
  while (idx < indent) {
  ++idx;
  #ifdef TEST
  CAMERA_STDOUT("\t");
  #else
  CAMERA_LOG("\t");
  #endif
  }
  }
*/

void print_camera_tree(file_node* root, int indent) 
{
        int i = 0;
        char buf[MAX_PAYLOAD];
	if (!root) return;	
        memset(buf, 0, MAX_PAYLOAD);
	FOR(i,0,indent) strcat(buf, "\t");
	strcat(buf, root->dentry->d_name.name);
#ifdef TEST
	CAMERA_STDOUT("%s", buf);
#else
	CAMERA_LOG("%s", buf);
#endif
	print_camera_tree(root->firstChd, indent+1);
	print_camera_tree(root->nextSib, indent);
}

file_node* __build_exclude_list(str_node* exclude_head) 
{
	file_node* tmp = NULL;
	file_node* excludeList = NULL;
	file_node* excludeListTail = NULL;
	struct nameidata nd;
	while (exclude_head) {
		if (!path_lookup(exclude_head->str, LOOKUP_FOLLOW, &nd)) {
			if (!excludeListTail) {
				excludeList = excludeListTail = kmalloc(sizeof(file_node), GFP_KERNEL);
				excludeListTail->nextSib = excludeListTail->firstChd = NULL;
				excludeListTail->dentry = nd.path.dentry;
			} else {
				tmp = kmalloc(sizeof(file_node), GFP_KERNEL);
				tmp->nextSib = tmp->firstChd = NULL;
				tmp->dentry = nd.path.dentry;
				excludeListTail->nextSib = tmp;
				excludeListTail = tmp;
			}
			path_put(&nd.path);
		}
		exclude_head = exclude_head->next;
	}
	return excludeList;
}

file_node* build_cow_tree(args* ag, void* elem)
{
	struct nameidata nd;
	file_node* root = NULL;
	file_node* excludeList = NULL;
	str_node* cameraPath = NULL;
	root = (file_node*)kmalloc(sizeof(file_node), GFP_KERNEL);
	memset(root, 0, sizeof(file_node));
	if (!ag || !root) goto out_failed;

	excludeList = __build_exclude_list(exclude_path_head);
	if (!path_lookup("/", LOOKUP_FOLLOW, &nd)) {
		root->dentry = nd.path.dentry;
		path_put(&nd.path);
	} else goto out_failed;

	cameraPath = camera_path_head;
	while (cameraPath) {
	        if (__addto_root_node(root, cameraPath, 
				      excludeList, filter_head, 
				      (args_queue_elem*)elem)) goto out_failed;

		cameraPath = cameraPath->next;
	}

	__releasefile_node(excludeList);	

#ifdef TEST
	if (read_test_code() == BUILD_TREE) print_camera_tree(root,0);
#endif
	return root;

out_failed:
	__releasefile_node(excludeList);	
	__releasefile_node(root);	
	return NULL;
}

int calc_tree_size(file_node* root)
{
	if (!root) return 0;
	return root->dentry->d_inode->i_size + 
	 	calc_tree_size(root->firstChd) + 
		calc_tree_size(root->nextSib);
}

typedef struct blk_node {
	struct super_block* sb;
#define dev sb->s_bdev->bd_dev
	sector_t blk;
	struct blk_node* mirror_node;
} blk_node;

blk_node* __alloc_node(struct inode* in, sector_t blk) 
{
	blk_node* node = (blk_node*)kmalloc(sizeof(blk_node), GFP_KERNEL);
	memset(node, 0, sizeof(blk_node));
	node->sb = in->i_sb;
	node->blk = blk;
	return node;
}

void release_blk_node (void* addr)
{
	kfree(addr);
}

int is_equal(void* left, void* right) 
{
	blk_node* left_n = (blk_node*)left;
	blk_node* right_n = (blk_node*)right;
	if (!left_n || !right_n) return 0;
	if (left_n->dev==right_n->dev &&
	    left_n->blk==right_n->blk) return 1;
	else return 0;
}

int is_bigger(void* left, void* right) 
{
	blk_node* left_n = (blk_node*)left;
	blk_node* right_n = (blk_node*)right;
	if (!left_n || !right_n) return 0;
	if (left_n->dev == right_n->dev) {
		if (left_n->blk > right_n->blk) return 1;
		else return 0;
	} else if (left_n->dev > right_n->dev) return 1;
	else return 0;
}

int is_smaller(void* left, void* right) 
{
	blk_node* left_n = (blk_node*)left;
	blk_node* right_n = (blk_node*)right;
	if (!left_n || !right_n) return 0;
	if (left_n->dev == right_n->dev) {
		if (left_n->blk < right_n->blk) return 1;
		else return 0;
	} else if (left_n->dev < right_n->dev) return 1;
	else return 0;
}

void copy(void* to, void* from)
{
	blk_node* to_n = (blk_node*)to;
	blk_node* from_n = (blk_node*)from;
	to_n->sb = from_n->sb;
	to_n->blk = from_n->blk;
	to_n->mirror_node = from_n->mirror_node;
}

void print_node(void* node) 
{
	CAMERA_LOG("%lu", ((blk_node*)node)->blk);
}

sbt alloc_sbt(void)
{
	sbt tree = (sbt)kmalloc(sizeof(self_balance_tree), GFP_KERNEL);
	memset(tree, 0, sizeof(self_balance_tree));
	spin_lock_init(&tree->lock);
	tree->release_key_fn = release_blk_node;
	tree->is_equal = is_equal;
	tree->is_smaller = is_smaller;
	tree->is_bigger = is_bigger;
	tree->copy = copy;
	tree->print_fn = print_node;
	return tree;
}

void record_blocks(void* from, void* to, sbt sbt_from, sbt sbt_to)
{
	//	handle_t* handle;
	sector_t blk_idx;
	blkcnt_t blk_cnt;
	blk_node *node_from, *node_to;
	struct inode* i_from = (struct inode*)from;
	struct inode* i_to = (struct inode*)to;
	if (!i_from || !i_to) goto out;

	blk_idx = 0;
	blk_cnt = i_from->i_blocks;
	while (blk_idx < blk_cnt) {
		sector_t ret_idx;
		if ((ret_idx=bmap(i_from, blk_idx)) == 0) {
		        ++blk_idx;
			break;
		}
		alloc_block(i_to, blk_idx, 1<<i_from->i_blkbits);
		++blk_idx;
	}

	blk_cnt = blk_idx;
	blk_idx = 0;
	while (blk_idx < blk_cnt) {
		sector_t blk_from = bmap(i_from, blk_idx);
		sector_t blk_to = bmap(i_to, blk_idx);
		if (blk_from && blk_to) {
		        //CAMERA_LOG("%lu -> %lu\n", blk_from, blk_to);
			node_from = __alloc_node(i_from, blk_from);
			node_to = __alloc_node(i_to, blk_to);
			node_from->mirror_node = node_to;
			node_to->mirror_node = node_from;
			insert_key(sbt_from, node_from);
			insert_key(sbt_to, node_to);
		}
		++blk_idx;
	}

	i_size_write(i_to, i_from->i_size);
	set_fs_inode_size(i_to, i_from->i_size);
	set_fs_inode_dirty(i_to);
out:
	return;
}

void __copy_block(blk_node* node_from, blk_node* node_to)
{
	struct buffer_head *bh_from, *bh_to;
	if (!node_from || !node_to) return;
	bh_from = sb_bread(node_from->sb, node_from->blk);
	bh_to = sb_bread(node_to->sb, node_to->blk);
	memcpy(bh_to->b_data, bh_from->b_data, bh_from->b_size);
	mark_buffer_dirty(bh_to);
	brelse(bh_from);
	brelse(bh_to);
}

void copy_blocks(args_queue_elem* elem)
{
	blk_node *node_from, *node_to;
	sbt sbt_from = elem->sbt_from, sbt_to = elem->sbt_to;
	
	if (!sbt_from || !sbt_to) goto out;

	while(1) {
		node_from = (blk_node*)get_first_key(sbt_from);
		if (!node_from) break;
		node_to = node_from->mirror_node;
		spin_lock(&elem->lock);
		__copy_block(node_from, node_to);
		elem->done += elem->block_size;
		remove_key(sbt_from, node_from);
		remove_key(sbt_to, node_to);
		spin_unlock(&elem->lock);
		schedule_timeout(msecs_to_jiffies(1000));
	}
out:
	return;
}

int camera_make_request(struct request_queue* q, struct bio* bio)
{
	blk_node bn;
	blk_node *node;
	args_queue_elem* elem = NULL;
	make_request_fn* fn = (make_request_fn*)lookup_fn(q);
	bn.sb = B2SB(bio); 
	bn.blk = bio->bi_sector;
	if (B2MP(bio)) elem = (args_queue_elem*)(B2IN(bio)->i_private);
	if (IS_ERR_OR_NULL(elem) || IS_ERR_OR_NULL(elem->sbt_from)) goto out;

	wait_event_interruptible(elem->frez_cond, 
				 atomic_read(&elem->should_freeze)==0);

	if (bio->bi_rw == WRITE) {
		node = (blk_node*)query_key(elem->sbt_from, &bn);
		if (node) {
			spin_lock(&elem->lock);
			__copy_block(node, node->mirror_node);
			elem->done += elem->block_size;
			remove_key(elem->sbt_from, node);
			remove_key(elem->sbt_to, node->mirror_node);
			spin_unlock(&elem->lock);
		}
	} else {
		node = (blk_node*)query_key(elem->sbt_to, &bn);
		if (node) {
			spin_lock(&elem->lock);
			__copy_block(node->mirror_node, node);
			elem->done += elem->block_size;
			remove_key(elem->sbt_from, node->mirror_node);
			remove_key(elem->sbt_to, node);
			spin_unlock(&elem->lock);
		}
	}
out:
	if (fn) return fn(q, bio);
	else {
		CAMERA_LOG("Error: camera found undefined make_request_fn!\n");
		return -1;
	}
}

void replace_make_request(struct super_block* sb, args_queue_elem* elem)
{
	make_request_fn* fn = MK_RQ_FN(sb);
	if (fn != camera_make_request) {
		struct super_block* ret_sb = freeze_bdev(sb->s_bdev);
		DELAY();
		append_fn(sb->s_bdev->bd_disk->queue, MK_RQ_FN(sb));
		MK_RQ_FN(sb) = camera_make_request;
		thaw_bdev(sb->s_bdev, ret_sb);
	}
}

void restore_make_request(struct super_block* sb)
{
	make_request_fn* fn = NULL;
	if (!sb) return;
	fn = (make_request_fn*)lookup_fn(sb->s_bdev->bd_disk->queue);
	if (fn && MK_RQ_FN(sb) == camera_make_request) {
		struct super_block* ret_sb = freeze_bdev(sb->s_bdev);	
		DELAY();
		MK_RQ_FN(sb) = fn;
		thaw_bdev(sb->s_bdev, ret_sb);	
	}
}

mk_fn_node* mk_fn_head = NULL;
spinlock_t mk_fn_lock;
void* lookup_fn(void* key)
{
	mk_fn_node *nd = mk_fn_head;
	spin_lock(&mk_fn_lock);
	while (nd) {
		if (nd->key == key) goto out;
		nd = nd->next;
	}
out:
	spin_unlock(&mk_fn_lock);
	return nd ? nd->fn : NULL;
}

void append_fn(void* key, make_request_fn* fn) 
{
	mk_fn_node* nd = NULL;
	spin_lock(&mk_fn_lock);
	if (!key || !fn) goto out;
	nd = (mk_fn_node*)kmalloc(sizeof(mk_fn_node), GFP_KERNEL);
	memset(nd, 0, sizeof(mk_fn_node));
	nd->key = key;
	nd->fn = fn;
	nd->next = mk_fn_head;
	mk_fn_head = nd;
out:
	spin_unlock(&mk_fn_lock);
	return;
}

void clean_fn(void)
{
	spin_lock(&mk_fn_lock);
	if (!mk_fn_head) goto out;
	while (mk_fn_head) {
		mk_fn_node* present = mk_fn_head;
		mk_fn_head = mk_fn_head->next;
		kfree(present);
	}
out:
	spin_unlock(&mk_fn_lock);
}
